// 题目：
//  从前有一只青蛙他想跳台阶，有n级台阶，青蛙一次可以跳1级台阶，也可以跳2级台阶；问：该青蛙跳到第n级台阶一共有多少种跳法
// 思路：
//    动态规划，每一次有且只有两种选择：可以选择跳1级或者2级
//     如果跳1级，剩下的问题就成了跳n-1级台阶的问题
//     如果跳2级，剩下的问题就成了跳n-2级台阶的问题
//     这样这个问题就转化成了一个更小的问题，可通过递推或者递归求解
#include <iostream>

using namespace std;

int fab(int n) {
  // 终止条件：1或2级台阶
  if (n == 1) return 1;  // 1级台阶：1
  if (n == 2) return 2;  // 2级台阶：1, 1 或者 2

  return fab(n - 1) + fab(n - 2);
}

int main(int argc, char** argv) {
  int n;
  cin >> n;
  if (n < 1) {
    cout << "n 必须 >= 1" << endl;
    exit(-1);
  }

  cout << n << "级台阶一共有 " << fab(n) << " 种跳法！" << endl;
  return 0;
}
